package com.mlh.dp.买卖股票的最佳时机;

/**
 * @author 缪林辉
 * @date 2024/4/24 22:51
 * @DESCRIPTION
 */
// 给定一个数组，它的第 i 个元素是一支给定的股票在第 i 天的价格。
// 设计一个算法来计算你所能获取的最大利润。你最多可以完成 !!两笔!! 交易。
// 注意：你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。
public class 买卖股票的最佳时机3 {
    //相对于 买卖股票的最佳时机2 这里限定死了只能进行两笔交易
    //想到了4种状态，但是数组的含义没想清楚，导致思路错乱了
    //dp[0][i]，表示的是第i天，买入股票的状态，并不是说一定要第i天买入股票，这是很多同学容易陷入的误区。 我就是陷入这个误区
    //利用重叠子问题思想 去理解
    public int method1(int[] prices) {
        int[][]dp=new int[4][prices.length];
        //初始化
        dp[0][0]=-prices[0];
        dp[2][0]=-prices[0];
        for (int i = 1; i <prices.length ; i++) {
            //可以看到每个位置之和自己上一行和前一列有关系，可以优化成滚动数组
            dp[0][i]=Math.max(dp[0][i-1],-prices[i]);
            dp[1][i]=Math.max(dp[0][i]+prices[i],dp[1][i-1]);
            dp[2][i]=Math.max(dp[1][i]-prices[i],dp[2][i-1]);
            dp[3][i]=Math.max(dp[2][i]+prices[i],dp[3][i-1]);
        }
        return dp[3][prices.length-1];
    }

    //优化成滚动数组
    public int method2(int[] prices) {
        int[]dp=new int[4];
        //初始化
        dp[0]=-prices[0];
        dp[2]=-prices[0];
        for (int i = 1; i <prices.length ; i++) {
            dp[0]=Math.max(dp[0],-prices[i]);
            dp[1]=Math.max(dp[0]+prices[i],dp[1]);
            dp[2]=Math.max(dp[1]-prices[i],dp[2]);
            dp[3]=Math.max(dp[2]+prices[i],dp[3]);
        }
        return dp[3];
    }

    public int practice(int[] prices) {
        int len=prices.length;
        int[][]dp=new int[len][4];
        dp[0][0]=-prices[0];
        dp[0][2]=-prices[0];
        for (int i = 1; i < len; i++) {
            dp[i][0]=Math.max(dp[i-1][0],-prices[i]);
            dp[i][1]=Math.max(dp[i-1][0]+prices[i],dp[i-1][1]);
            dp[i][2]=Math.max(dp[i-1][2],dp[i-1][1]-prices[i]);
            dp[i][3]=Math.max(dp[i-1][2]+prices[i],dp[i-1][3]);
        }
        return dp[len-1][3];
    }
}
